#! /usr/bin/env python
__author__="Hong Phuc Bui, Sarah Theobald "
__date__ ="$Dec 20, 2011 10:54:44 AM$"

__description__ = '''
Diese Module enthaelt alle Funktionen und Klassen um Pollard :math:`\lambda` Problem zu loesen.
'''

import random
import time

import logging

logger = logging.getLogger(__file__)
logger.setLevel(logging.ERROR)


NUM_OF_ZERO_BIT = 8
u'''
	Anzahl der lezten Bits einer Element der Pollard Reihe, die 0 betragen. Die optinale Werten sind:

	+-------------------------------------+--------------------+
	|Groesse der Primzahl :math:`p` (Bit) | ``NUM_OF_ZERO_BIT``|
	+=====================================+====================+
	|10                                   | 2                  |
	+-------------------------------------+--------------------+
	|14                                   | 3                  |
	+-------------------------------------+--------------------+
	|27                                   | 8                  |
	+-------------------------------------+--------------------+
	|50                                   | 10                 |
	+-------------------------------------+--------------------+

	Die Werten werden mit einem Intel 2 Core Prozessor (jeweils 2.17 GHz) erfasst und koennen in
	andere Prozessoren variieren. Geschaetzte Wert ist gegen ein Dritte der Groese der Primzahl :math:`p`.
'''

def extgcd(a, b):#
	'''
	berechnet die groest gemeinsam Teiler von zwei Zahlen :math:`a` und :math:`b`.

	:param a: die Zahl :math:`a`
	:param b: die Zahl :math:`b`
	:return: ein Tupel :math:`(d, u, v)` so dass

		* :math:`d, u, v` sind Integer
		* :math:`d` ist der ggT von :math:`a` und :math:`b`
		* :math:`a\cdot u + b\cdot v = d`

	'''
	u=t=1
	v=s=0
	while b>0:
		q=a//b
		a, b = b, a-q*b
		u, s = s, u-q*s
		v, t = t, v-q*t
	return a, u, v

def invers(a,n):#
	'''
	berechnet die Invers von :math:`a` in :math:`\mod n`.

	:param a: die Zahl :math:`a`
	:param n: die Zahl :math:`n`
	:return: eine Zahl :math:`x` so dass :math:`a\cdot x \equiv 1 \mod n`
	'''
	(ggt, u, v) = extgcd(a,n)
	if ggt != 1:
		return None
	else:
		return u % n
	
	
def chinese(x_1, x_2, q):#
	'''
	Berechnet die sonder Fall von chinesische Restsatz.

	:param x_1:
	:param x_2:
	:param q: eine Primzahl
	:return: ein Zahl :math:`x` so dass
		:math:`x \equiv x_1 \mod q` und :math:`x \equiv x_2 \mod 2`. Es
		bedeutet
		:math:`x\mod q == x_1` und :math:`x\mod 2 = x_2`


	'''
	x = (x_1 * 2 * invers(2,q) + x_2 * q * invers(q,2) ) % (2*q)
	return x
	

def powerMod(b,e,m):#
	'''
		berechnet :math:`b^e \mod m`
		
		:param b: integer Wert
		:param e: integer Wert
		:param m: integer Wert
	'''
	r = 1
	while e != 0:
		if (e & 1) == 1:
			r = (r*b) % m
		e = e >> 1
		b = (b*b) % m
	
	return r

def searchFirstErzeuger(p, factor):#
	'''
	
searches the first generator in the group :math:`\mathbf{F}_p \setminus \{0\}`

:param p:	  eine Primzahl
:param factor: 2-Dimensionale Array von Prime-Faktoren von ``p-1``, in Format ``[[p_1,e_1] , [p_2, e_2] ... ]``.
	Dabei sind ``p_1``, ``p_2``, ... die Primen, ``e_1``, ``e_2``, ... die entsprechenden Exponenten.

	'''
	
	isErzeuger = True
	g = 0
	while g <= p-1:
		g +=1; 
	#for g in range(1,p):
		# logger.debug( "g = %d" %g
		isErzeuger = True
		for i in range(0,len(factor)):
			# logger.debug( "\t p_i = %d" %factor[i][0]
			e = (p-1)/factor[i][0]
			# logger.debug( "\t e = %d" %e
			r = powerMod(g, e, p)
			# logger.debug( "\t r = %d" %r
			if r == 1:
				isErzeuger = False
				break;
			
		if isErzeuger:
			return g



def checkDistinguishPoint(y,k=0,l=0):#
	'''
		ueberprueft, ob ``y`` ein `distinguish Point` ist
		Diese Funktion wird als platzhalter in Client verwendet
		
		:param y: den Wert zu ueberpruefen
		:param k: Wenn andere Kriterien verwendet werden soll, und er braucht
			nicht nur ``y``, sondern auch ``k`` und ``l`` (Im Fall der weiter Entwicklung).

		:param l: s.o.
		:return: Wenn ``y`` ein distinguish Point ist wird ein `True` zurueck geliefrt, sonst ``False``
	'''
	#time.sleep(0.25)
	#return True
		
	if y % (1<<NUM_OF_ZERO_BIT) == 0:
		return True
	else:
		return False
	

def calculateDLFromCollision(k_i, l_i, k_j, l_j, q):#
	'''
	Loest das DL Problem :math:`g^x \equiv h \mod p` aus Pollard Kollision (probabilistisch).
	Wobei :math:`p = 2q + 1`, :math:`q` ist auch eine Primzahl.

	:param k_i: Die Zahl :math:`k_i`
	:param l_i: Die Zahl :math:`l_i`
	:param k_j: Die Zahl :math:`k_j`
	:param l_j: Die Zahl :math:`l_j`
	:param q:   Die Primzahl :math:`q`
	:return: Wenn ``l_i - l_j`` ein Vielfache von 2 ist, wird ``None`` zurueck geliefert,
		sonst wird die Loesung aus Kollision berechnet und das Ergebnis zurueck geliefert.
	'''
	if ((l_i - l_j) % 2 == 0 ):
		logger.warning( "Vielfache! muss weiterrechnen!")
		return None
	else:
		x1 = k_j - k_i
		x2 = l_i -l_j
		x = ((x1 % (2*q)) * invers(x2, 2*q)) % (2*q)
		return x

	pass

class PollardSeries():
	def __init__(self, g, h, p):
		'''
Calculate Pollard Element of Pollard Series in :math:`g^x = h \mod p` 

:param g: Erzeuger der Klasse :math:`\mathbf{F}_p`
:param h: Ein Element :math:`h \in \mathbf{F}_p`
:param p: Primzahl :math:`p`
			
		'''
		
		self.g = g
		self.h = h
		self.p = p
		self.q = (p-1)/2
		# init random values (k und l)
		self.k = random.randint(0, self.p-1)
		self.l = random.randint(0, self.p-1)
		
		# init y_0 = g^k * h^l mod p (ist ziemlich egal, was zu initialisiert)
		tmp_1 = powerMod(self.g, self.k, self.p)
		tmp_2 = powerMod(self.h, self.l, self.p)
		self.y = (tmp_1*tmp_2) % self.p
		logger.debug( "          (y = %d, k = %d, l= %d)"%(self.y, self.k, self.l) )

	
	
	def computeNextElement(self):#
		'''
			berechnet die naechste Element der Pollard Reihe.
			@return eine Tupel :math:`(y,k,l)` so dass :math:`y = k\cdot l \mod p`
		'''
		rest = self.y % 3
		if rest == 0:
			self.k = (self.k * 2)      % (self.p -1)
			self.l = (self.l * 2)      % (self.p -1)
			self.y = (self.y * self.y) % self.p
			logger.debug( "rest = %d (y = %d, k = %d, l= %d)"%(rest, self.y, self.k, self.l) )
		elif rest == 1:
			self.y = (self.g * self.y) % self.p
			self.k = (self.k + 1)      % (self.p-1)
			logger.debug( "rest = %d (y = %d, k = %d, l= %d)"%(rest, self.y, self.k, self.l) )

		elif rest == 2:
			self.y = (self.h * self.y) % self.p
			self.l = (self.l + 1)      % (self.p-1)
			logger.debug( "rest = %d (y = %d, k = %d, l= %d)"%(rest, self.y, self.k, self.l) )

		
		return (self.y, self.k, self.l)
	
	




'''
test code fuer extgdc
if __name__ == "__main__":
	x = extgcd(11,111)
	logger.debug( x
	
	e = invers(5, 23)
	logger.debug( e
	
	r = chinese(3,1,5)
	logger.debug( r
'''	
	
	